package practise;

import java.util.Stack;

public class IsSymmetric {
    public static boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }

        Stack<TreeNode> stackLeft = new Stack<>();
        Stack<TreeNode> stackRight = new Stack<>();
        TreeNode nodeLeft = root.left;
        TreeNode nodeRight = root.right;

        stackLeft.push(root.left);
        stackRight.push(root.right);

        while(!stackLeft.isEmpty() && !stackRight.isEmpty()) {
            nodeLeft = stackLeft.pop();
            nodeRight = stackRight.pop();
            if(nodeLeft == null && nodeRight == null) {
                continue;
            }
            if(nodeLeft == null || nodeRight == null) {
                return false;
            }
            if(nodeLeft.val != nodeRight.val) {
                return false;
            }
            stackLeft.push(nodeLeft.left);
            stackLeft.push(nodeLeft.right);
            stackRight.push(nodeRight.right);
            stackRight.push(nodeRight.left);
        }
        return stackLeft.isEmpty() && stackRight.isEmpty();
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);
        isSymmetric(root);
    }
}
